package com.gitee.feizns.explore.data_structure.linked_list.singly.palindrome;

/**
 * @author feizns
 * @since 2019/10/8
 */
public class Main {

    public static void main(String[] args) {
        ListNode node = ListNode.create();
        System.out.println(isPalindrome(node));
//        node.print();
//
//        System.out.println(findPrev(node, node.next));
//         = node.next;
//        ListNode reverse = reverse(node, node.next.next);
//        reverse.print();

//        node.print();
//        reverse(node, node).print();
//        node.print();
    }

    public static boolean isPalindrome(ListNode head) {
        if ( head == null || head.next == null )
            return true;

        ListNode slow = head;
        ListNode fast = head;
        ListNode prev = head;
        ListNode curtHeader = head;

        while ( fast != null && fast.next != null ) {
            slow = slow.next;
            fast = fast.next.next;
            if ( fast != null ) {
                ListNode slowNext = slow.next;
                slow.next = curtHeader;
                prev.next = slowNext;
                curtHeader = slow;
                slow = prev;
                prev = slowNext;
            }
        }

        ListNode left = curtHeader;
        while ( slow != null ) {
            if ( left.val != slow.val )
                return false;
            left = left.next;
            slow = slow.next;
        }
        return true;
    }

    private static void reverse(ListNode head) {

    }


//    public static boolean isPalindrome(ListNode head) {
//        if ( head == null || head.next == null )
//            return true;
//
//        ListNode slow = head;
//        ListNode fast = head;
//        while ( slow != null && fast != null && fast.next != null ) {
//            slow = slow.next;
//            fast = fast.next.next;
//        }
//
//        if ( slow != fast ) {
//            ListNode left = reverse(head, slow);
//            ListNode right = fast != null ? slow.next : slow;
//            while (left != slow) {
//                if ( left.val != right.val )
//                    return false;
//                left = left.next;
//                right = right.next;
//            }
//            return true;
//        }
//        return false;
//    }
//
//    public static ListNode reverse(ListNode head, ListNode end) {
//        if ( head != end ) {
//            ListNode prev = head;
//            ListNode curt = head.next;
//            head.next = end;
//            while ( curt != end ) {
//                ListNode next = curt.next;
//                curt.next = prev;
//                prev = curt;
//                curt = next;
//            }
//            return prev;
//        }
//        return null;
//    }

}
